<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>覆盖问题 | 小熊的技术文档</title>
    <meta name="generator" content="VuePress 1.8.2">
    <link rel="icon" href="/fav.ico">
    <link rel="stylesheet" href="/css/katex.min.css">
    <link rel="stylesheet" href="/css/github-markdown.min.css">
    <meta name="description" content="衣带渐宽终不悔，为伊消得人憔悴">
    
    <link rel="preload" href="/assets/css/0.styles.e6449353.css" as="style"><link rel="preload" href="/assets/js/app.9e067b79.js" as="script"><link rel="preload" href="/assets/js/2.983eb755.js" as="script"><link rel="preload" href="/assets/js/51.f6160d52.js" as="script"><link rel="prefetch" href="/assets/js/10.79548333.js"><link rel="prefetch" href="/assets/js/11.31600f80.js"><link rel="prefetch" href="/assets/js/12.62bd3528.js"><link rel="prefetch" href="/assets/js/13.de8b1ace.js"><link rel="prefetch" href="/assets/js/14.f5db1e75.js"><link rel="prefetch" href="/assets/js/15.bf827d4d.js"><link rel="prefetch" href="/assets/js/16.cc9a1a73.js"><link rel="prefetch" href="/assets/js/17.2cfaefeb.js"><link rel="prefetch" href="/assets/js/18.3af7782b.js"><link rel="prefetch" href="/assets/js/19.639f7e7b.js"><link rel="prefetch" href="/assets/js/20.dc862f59.js"><link rel="prefetch" href="/assets/js/21.916e1685.js"><link rel="prefetch" href="/assets/js/22.d7a955f4.js"><link rel="prefetch" href="/assets/js/23.078391ef.js"><link rel="prefetch" href="/assets/js/24.bb460a5a.js"><link rel="prefetch" href="/assets/js/25.d69f2326.js"><link rel="prefetch" href="/assets/js/26.6da7ea48.js"><link rel="prefetch" href="/assets/js/27.82e23d91.js"><link rel="prefetch" href="/assets/js/28.9073bbec.js"><link rel="prefetch" href="/assets/js/29.639259a4.js"><link rel="prefetch" href="/assets/js/3.e594e5b2.js"><link rel="prefetch" href="/assets/js/30.b49c622d.js"><link rel="prefetch" href="/assets/js/31.92f6c8b3.js"><link rel="prefetch" href="/assets/js/32.42419088.js"><link rel="prefetch" href="/assets/js/33.c82e2ab8.js"><link rel="prefetch" href="/assets/js/34.381de37e.js"><link rel="prefetch" href="/assets/js/35.5e86d478.js"><link rel="prefetch" href="/assets/js/36.31f218ce.js"><link rel="prefetch" href="/assets/js/37.0d287b3f.js"><link rel="prefetch" href="/assets/js/38.1324cf44.js"><link rel="prefetch" href="/assets/js/39.de6bdb51.js"><link rel="prefetch" href="/assets/js/4.440c4dd9.js"><link rel="prefetch" href="/assets/js/40.a22c9c27.js"><link rel="prefetch" href="/assets/js/41.4637d617.js"><link rel="prefetch" href="/assets/js/42.db815e2b.js"><link rel="prefetch" href="/assets/js/43.f0955a92.js"><link rel="prefetch" href="/assets/js/44.7d5faddf.js"><link rel="prefetch" href="/assets/js/45.a88ffc33.js"><link rel="prefetch" href="/assets/js/46.883caa71.js"><link rel="prefetch" href="/assets/js/47.6f2cfd60.js"><link rel="prefetch" href="/assets/js/48.ea25654e.js"><link rel="prefetch" href="/assets/js/49.f38c23a0.js"><link rel="prefetch" href="/assets/js/5.e8844f36.js"><link rel="prefetch" href="/assets/js/50.e03dd8e9.js"><link rel="prefetch" href="/assets/js/52.4daa8322.js"><link rel="prefetch" href="/assets/js/53.b30992e9.js"><link rel="prefetch" href="/assets/js/54.209f17e1.js"><link rel="prefetch" href="/assets/js/55.4f1dd95b.js"><link rel="prefetch" href="/assets/js/56.147ea3e8.js"><link rel="prefetch" href="/assets/js/57.5823e0e2.js"><link rel="prefetch" href="/assets/js/58.772320f9.js"><link rel="prefetch" href="/assets/js/59.5ab55a80.js"><link rel="prefetch" href="/assets/js/6.54e1cc95.js"><link rel="prefetch" href="/assets/js/60.b47b75bb.js"><link rel="prefetch" href="/assets/js/61.0cd5a012.js"><link rel="prefetch" href="/assets/js/62.35eb5453.js"><link rel="prefetch" href="/assets/js/63.d31f2118.js"><link rel="prefetch" href="/assets/js/64.03d35d7c.js"><link rel="prefetch" href="/assets/js/65.8bdc633f.js"><link rel="prefetch" href="/assets/js/66.dbbe8867.js"><link rel="prefetch" href="/assets/js/67.228613b5.js"><link rel="prefetch" href="/assets/js/68.d10a2687.js"><link rel="prefetch" href="/assets/js/69.7903847f.js"><link rel="prefetch" href="/assets/js/7.f5ab00eb.js"><link rel="prefetch" href="/assets/js/70.11ee4e27.js"><link rel="prefetch" href="/assets/js/8.95b39934.js"><link rel="prefetch" href="/assets/js/9.26cfd48c.js">
    <link rel="stylesheet" href="/assets/css/0.styles.e6449353.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">小熊的技术文档</span></a> <div class="links"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><a href="/front-end/" class="nav-link">
  🎨前端
</a></div><div class="nav-item"><a href="/back-end/" class="nav-link">
  💻后端
</a></div><div class="nav-item"><a href="/practice/" class="nav-link">
  🚀实战
</a></div><div class="nav-item"><a href="/office/" class="nav-link">
  🏢办公
</a></div><div class="nav-item"><a href="/general/" class="nav-link">
  🍓通用
</a></div><div class="nav-item"><a href="/paper/" class="nav-link router-link-active">
  🐸论文
</a></div><div class="nav-item"><a href="/general/fast.html" class="nav-link">
  ⚡快速笔记
</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="🦉近期重点" class="dropdown-title"><span class="title">🦉近期重点</span> <span class="arrow down"></span></button> <button type="button" aria-label="🦉近期重点" class="mobile-dropdown-title"><span class="title">🦉近期重点</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/back-end/python.html" class="nav-link">
  🐇python常用模块
</a></li><li class="dropdown-item"><!----> <a href="/practice/zrender.html" class="nav-link">
  🌹zrender源码解析
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="⭐️资源" class="dropdown-title"><span class="title">⭐️资源</span> <span class="arrow down"></span></button> <button type="button" aria-label="⭐️资源" class="mobile-dropdown-title"><span class="title">⭐️资源</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="https://www.birdiesearch.com/" target="_blank" rel="noopener noreferrer" class="nav-link external">
  小鸟搜索
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></li><li class="dropdown-item"><!----> <a href="https://salttiger.com/" target="_blank" rel="noopener noreferrer" class="nav-link external">
  每天一本编程书
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></li><li class="dropdown-item"><!----> <a href="https://gitee.com/docmirror/dev-sidecar" target="_blank" rel="noopener noreferrer" class="nav-link external">
  开发者边车
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></li></ul></div></div> <!----></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><nav class="nav-links"><div class="nav-item"><a href="/front-end/" class="nav-link">
  🎨前端
</a></div><div class="nav-item"><a href="/back-end/" class="nav-link">
  💻后端
</a></div><div class="nav-item"><a href="/practice/" class="nav-link">
  🚀实战
</a></div><div class="nav-item"><a href="/office/" class="nav-link">
  🏢办公
</a></div><div class="nav-item"><a href="/general/" class="nav-link">
  🍓通用
</a></div><div class="nav-item"><a href="/paper/" class="nav-link router-link-active">
  🐸论文
</a></div><div class="nav-item"><a href="/general/fast.html" class="nav-link">
  ⚡快速笔记
</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="🦉近期重点" class="dropdown-title"><span class="title">🦉近期重点</span> <span class="arrow down"></span></button> <button type="button" aria-label="🦉近期重点" class="mobile-dropdown-title"><span class="title">🦉近期重点</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/back-end/python.html" class="nav-link">
  🐇python常用模块
</a></li><li class="dropdown-item"><!----> <a href="/practice/zrender.html" class="nav-link">
  🌹zrender源码解析
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="⭐️资源" class="dropdown-title"><span class="title">⭐️资源</span> <span class="arrow down"></span></button> <button type="button" aria-label="⭐️资源" class="mobile-dropdown-title"><span class="title">⭐️资源</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="https://www.birdiesearch.com/" target="_blank" rel="noopener noreferrer" class="nav-link external">
  小鸟搜索
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></li><li class="dropdown-item"><!----> <a href="https://salttiger.com/" target="_blank" rel="noopener noreferrer" class="nav-link external">
  每天一本编程书
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></li><li class="dropdown-item"><!----> <a href="https://gitee.com/docmirror/dev-sidecar" target="_blank" rel="noopener noreferrer" class="nav-link external">
  开发者边车
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></li></ul></div></div> <!----></nav>  <ul class="sidebar-links"><li><a href="/paper/writing.html" class="sidebar-link">论文写作</a></li><li><a href="/paper/search.html" class="sidebar-link">无人机搜索</a></li><li><a href="/paper/defense.html" class="sidebar-link">防御无人机</a></li><li><a href="/paper/cover.html" aria-current="page" class="active sidebar-link">覆盖问题</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/paper/cover.html#【2020】无线传感器网络中目标覆盖问题的传感器部署方法" class="sidebar-link">💎【2020】无线传感器网络中目标覆盖问题的传感器部署方法</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/paper/cover.html#传感器部署方法引言" class="sidebar-link">传感器部署方法引言</a></li><li class="sidebar-sub-header"><a href="/paper/cover.html#传感器部署方法相关工作" class="sidebar-link">传感器部署方法相关工作</a></li><li class="sidebar-sub-header"><a href="/paper/cover.html#网络生存期的上界和问题定义" class="sidebar-link">网络生存期的上界和问题定义</a></li><li class="sidebar-sub-header"><a href="/paper/cover.html#本文的提出的粒子群优化方法" class="sidebar-link">本文的提出的粒子群优化方法</a></li></ul></li><li class="sidebar-sub-header"><a href="/paper/cover.html#cpso-算法" class="sidebar-link">CPSO 算法</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/paper/cover.html#原始-pso-算法和名词解释" class="sidebar-link">原始 PSO 算法和名词解释</a></li><li class="sidebar-sub-header"><a href="/paper/cover.html#cpso-sk-算法" class="sidebar-link">CPSO-SK 算法</a></li></ul></li></ul></li><li><a href="/paper/2020Auguest.html" class="sidebar-link">2020年8月归档</a></li><li><a href="/paper/daily.html" class="sidebar-link">每天一篇SCI论文</a></li><li><a href="/paper/technology.html" class="sidebar-link">国防科技框架</a></li><li><a href="/paper/strategy.html" class="sidebar-link">国防科技策略2030</a></li><li><a href="/paper/mpc.html" class="sidebar-link">模型预测控制</a></li><li><a href="/paper/MARL.html" class="sidebar-link">多智能体强化学习论文集</a></li><li><a href="/paper/UAV.html" class="sidebar-link">无人机</a></li><li><a href="/paper/clustering.html" class="sidebar-link">常用聚类算法</a></li></ul> </aside> <main class="page"> <div class="theme-default-content content__default"><h1 id="覆盖问题"><a href="#覆盖问题" class="header-anchor">#</a> 覆盖问题</h1> <h2 id="【2020】无线传感器网络中目标覆盖问题的传感器部署方法"><a href="#【2020】无线传感器网络中目标覆盖问题的传感器部署方法" class="header-anchor">#</a> 💎【2020】无线传感器网络中目标覆盖问题的传感器部署方法</h2> <blockquote><p>摘要：传感器部署是无线传感器网络（WSNs）中的一个基本问题。对覆盖问题的研究主要集中在部署传感器来覆盖确定的区域或一组确定的点（目标）。另一方面，传感器网络的生命周期应该足够长，以满足应用需求。因此，在设计覆盖确定点的无线传感器网络解决方案时，必须考虑延长网络生命周期。确定传感器节点的位置以使目标被覆盖并使网络寿命最大化的问题称为传感器部署问题。目前，已有各种方法，如启发式算法和近似算法，来解决无线传感器网络中的传感器部署问题。本文采用两种改进的粒子群算法（PSO）来解决传感器部署问题。第一种算法是合作粒子群算法，第二种算法是基于模糊逻辑的改进型合作粒子群算法。仿真结果表明，与其他同类算法相比，本文提出的算法解决了网络生存期较长的目标覆盖问题。</p></blockquote> <h3 id="传感器部署方法引言"><a href="#传感器部署方法引言" class="header-anchor">#</a> 传感器部署方法引言</h3> <p>无线传感器网络是由分布在特定区域的大量传感器节点组成的。无线传感器网络的主要任务是处理从传感器收集的数据，以监测区域内的事件。在无线传感器网络中，传感器节点从该区域收集数据并将其发送到基站（也称为接收器）。无线传感器网络对许多军事和民用应用（如战场监视、安全和灾害管理）的效率有着重要的影响。然而，传感器节点有其自身的局限性，如能量、通信范围、处理和存储限制。无线传感器网络的网络生存期是指所需区域或点不再被覆盖的持续时间。**网络生存期（network lifetime）**是决定无线传感器网络效率的一个非常重要的标准。影响网络生命周期缩短的主要因素之一是网络中传感器节点的高功耗或能量消耗不均衡。这是因为每个传感器节点的电源都是一个电池，由于被覆盖区域的状况，可能无法再充电或更换。因此，需要对整个网络的能量消耗进行控制和均衡，以提高网络的生存期。因此，这些网络中使用的算法必须考虑传感器节点的能量消耗。</p> <p>无线传感器网络在覆盖一个区域时，对该区域的监测需要一定的可靠性。因此，以传感器节点在网络中的位置为基本输入的无线传感器网络中的覆盖问题已经被定义。一般来说，覆盖问题可以分为两类：区域覆盖问题和目标覆盖问题。区域覆盖问题集中在对整个期望空间的监控上，而目标覆盖问题则集中在对区域内某些特定点的监控上。目标覆盖问题可以分为以下几类：</p> <ol><li>简单覆盖：在这个问题中，每个目标都必须由至少一个传感器监控。</li> <li>K-覆盖：在这个问题中，每个目标至少应该被<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.69444em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.03148em;">k</span></span></span></span>个传感器节点监控。其中<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.69444em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.03148em;">k</span></span></span></span>是一个预先确定的常数整数。</li> <li>Q-覆盖：在这个问题中，目标<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>T</mi><mo>=</mo><mo>{</mo><msub><mi>T</mi><mn>1</mn></msub><mo separator="true">,</mo><msub><mi>T</mi><mn>2</mn></msub><mo separator="true">,</mo><mo>⋯</mo><mo separator="true">,</mo><msub><mi>T</mi><mi>n</mi></msub><mo>}</mo></mrow><annotation encoding="application/x-tex">T=\{T_1, T_2, \cdots , T_n\}</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.13889em;">T</span><span class="mrel">=</span><span class="mopen">{</span><span class="mord"><span class="mord mathit" style="margin-right:0.13889em;">T</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.13889em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.13889em;">T</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.13889em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="minner">⋯</span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.13889em;">T</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.13889em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">n</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mclose">}</span></span></span></span>的向量必须由<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>Q</mi><mo>=</mo><mo>{</mo><msub><mi>q</mi><mn>1</mn></msub><mo separator="true">,</mo><msub><mi>q</mi><mn>2</mn></msub><mo separator="true">,</mo><mo>⋯</mo><mo separator="true">,</mo><msub><mi>q</mi><mi>n</mi></msub><mo>}</mo></mrow><annotation encoding="application/x-tex">Q=\{q_1, q_2, \cdots, q_n\}</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit">Q</span><span class="mrel">=</span><span class="mopen">{</span><span class="mord"><span class="mord mathit" style="margin-right:0.03588em;">q</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.03588em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.03588em;">q</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.03588em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="minner">⋯</span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.03588em;">q</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.03588em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">n</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mclose">}</span></span></span></span>个传感器节点的数量来监控，这样目标<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>T</mi><mi>j</mi></msub></mrow><annotation encoding="application/x-tex">T_j</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.969438em;vertical-align:-0.286108em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit" style="margin-right:0.13889em;">T</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.13889em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit" style="margin-right:0.05724em;">j</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span>至少由<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>q</mi><mi>j</mi></msub></mrow><annotation encoding="application/x-tex">q_j</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.716668em;vertical-align:-0.286108em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit" style="margin-right:0.03588em;">q</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.03588em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit" style="margin-right:0.05724em;">j</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span>个传感器节点来监控，其中<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">n</span></span></span></span>是目标的数量，且<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>1</mn><mo>≤</mo><mi>j</mi><mo>≤</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">1 \le j \le n</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.65952em;"></span><span class="strut bottom" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">1</span><span class="mrel">≤</span><span class="mord mathit" style="margin-right:0.05724em;">j</span><span class="mrel">≤</span><span class="mord mathit">n</span></span></span></span>。</li></ol> <p>在 Chaudhary 和 Pujari 等人的研究中，他们展示了可以根据传感器节点的位置，对 WSN 的网络生存期的上界（upper bound)进行数学计算。该界可用于计算节点的位置，使网络获得两个性质：满足覆盖条件和最大化网络生存期。确定传感器节点的位置以使网络具有上述特性的问题称为传感器部署问题，这是一个<em>NP-hard</em>问题。</p> <p>到目前为止，已经有很多方法被提出来解决这个问题，比如粒子群优化算法(PSO)，人工蜂群(ABC)和遗传算法(GA)，这些方法将在下一节中解释。 然而，这些方法都是近似方法，每一种方法都能得到问题的近似解。 另一方面，由于这个问题是一个 NP-hard 问题，因此没有一个精确的多项式时间算法来解决这个问题。 因此，总是希望找到一个更好的近似值来解决这个问题。</p> <p>在本文中，我们使用两个改进的粒子群算法来解决传感器部署问题。 第一个版本是协作粒子群算法(den Bergh and Engelbrecht 2004) ，它是粒子群算法的改进版本。<br>
第二种是基于模糊逻辑的协同粒子群算法(Neshat 2013) ，其中每个粒子速度方程中的加速系数采用模糊逻辑控制。 在(den Bergh and Engelbrecht 2004; Neshat 2013)中，已经证明这些改进版本的粒子群优化算法比传统的粒子群优化算法产生更好的结果。这是因为这些改进的版本试图控制探索和开发之间的平衡，其中环境本身会随着时间的推移而动态变化。粒子群优化算法不能动态地适应变化的环境，在迭代的第一阶段很快收敛到最优解。 此外，原始粒子群优化算法的另一个主要缺点是，它可能会陷入一个次优解区域，并且对于高维问题而言，这个问题通常会变得更加困难。 利用这两种改进的粒子群优化算法，较好地解决了无线传感器网络中的传感器部署问题。 仿真结果表明，与其他同类算法相比，改进的粒子群算法能够更好地解决传感器部署问题，提高网络生命周期。 本文的主要特点和贡献突出如下：</p> <ul><li>利用改进的粒子群优化算法(PSO) ，通过协作粒子群优化算法，解决了传感器部署问题的多种版本、简单覆盖、 K-覆盖和 Q-覆盖问题。</li> <li>针对传感器部署问题，提出了粒子群优化算法中粒子速度方程中加速度系数的模糊控制方法。</li> <li>利用改进的协同粒子群优化算法，采用模糊逻辑系统控制加速度系数，解决了多种传感器配置问题</li> <li>给出了算法的仿真结果，仿真结果表明，与其他类似算法相比，提出的算法延长了网络生命周期。</li></ul> <p>论文的其余部分安排如下: 下一节将描述以前有关无线传感器网络覆盖问题的工作。 第三部分给出了网络生命周期上界的数学计算和传感器部署问题。 第四部分描述了用协同粒子群算法和模糊逻辑算法相结合来解决传感器部署问题。 这些算法在不同场景下的仿真结果在第 5 节中进行了描述。 最后，对第六部分的工作进行了总结，并展望了未来的研究方向。</p> <h3 id="传感器部署方法相关工作"><a href="#传感器部署方法相关工作" class="header-anchor">#</a> 传感器部署方法相关工作</h3> <p>到目前为止，针对无线传感器网络中的传感器部署问题，已经提出了各种解决方案。 这个部分介绍了其中一些与我们的工作最相关的方法。</p> <p>Elhoseny 等人(2017)利用遗传算法(GA)解决了无线传感器网络中的 k-覆盖问题。他们关注的是网络中的能源消耗。该算法考虑了目标位置、预期能量消耗和各传感器的覆盖范围等不同因素。然而，在遗传算法的适应度函数中没有考虑网络生命周期，这意味着该算法没有考虑延长网络生命周期。</p> <p>Lu 等人(2014)解决了无线传感器网络中的简单覆盖问题。 他们的主要目标是延长网络生命周期。<br>
为了达到这个目的，他们使用一个多项式时间逼近方案来调度传感器节点的清醒和睡眠状态。 提出的近似演算法协议提高了网络的生命周期。 然而，他们还没有解决传感器部署问题。</p> <p>Njoya 等人(2017)基于一种定义可移动、合并、重组和爆炸虚拟节点的新方法，解决了无线传感器网络中的简单覆盖问题。 这种方法被称为虚拟传感器，在保持完全覆盖的同时减少了实际传感器的数量。 但是，它的目标并不是最大化网络生存期。</p> <p>Ozdag (2018)基于类电磁(EM)算法解决了无线传感器网络中的 q 覆盖问题。Em 算法是一种基于粒子间电磁吸引和排斥的新型进化算法。 通过仿真，将该算法与该算法进行了比较。该算法是在 2018 年提出的，并与 2016 年提出的粒子群优化算法进行了比较。 仿真结果表明，在传感器节点少于 250 个、目标少于 25 个的情景下，EM 算法的性能优于本文提出的 PSO 算法(özda 和 karc 2016)。</p> <p>Cheng 和 Wang (2017)定义了一种新的目标覆盖问题，称为无线传感器网络中的目标障碍覆盖问题。 在这个问题中，对于每个目标，定义一个目标障碍物，它是在目标周围形成的连续的圆形障碍物。 他们用最少的传感器节点来构造目标屏障，解决了这个问题。 Yu 等人(2017)通过使用集中式和分布式协议解决了无线传感器网络中的 k 覆盖问题。 这些协议考虑了剩余能量和较低的传感器空间密度，解决了这个问题。 然而，(Cheng and Wang 2017)和(Yu et al. 2017)没有考虑传感器部署问题，这意味着他们不确定传感器节点的位置。</p> <p>Binh 等人(2018)已经解决了无线传感器网络的区域覆盖问题。本文采用了一种改进的布谷鸟搜索算法和混沌花授粉算法来解决这一问题。 这些算法改进了局部搜索算法，使算法得到了改进，问题得到了较好的解决。 仿真结果表明，这两种算法具有较好的区域覆盖率。 但是，它们并不解决传感器部署问题。</p> <p>Mini 等人(2013 年)已经研究了简单覆盖，k 覆盖和 q 覆盖问题在无线传感器网络。他们通过使用一个贪婪的启发式的人工蜜蜂群体(ABC)和粒子群优化群体(PSO)算法来解决这些问题。 这些算法的主要目标是最大化网络生命周期。 在这些算法中，粒子群算法为这些问题提供了更好的解决方案。</p> <p>Mansour 和 Jarray (2015)通过使用一个近似演算法数据库解决了无线传感器网络的区域覆盖问题。这个算法是基于线性规划。 首先，他们将问题转化为一个整数 / 线性规划问题，然后通过迭代和松弛技术得到问题的近似答案。 然而，解决线性规划问题最好也是最常用的方法是椭球算法。椭球算法虽然运行在多项式时间内，但实际上速度很慢。 尽管如此，它仍然是开发求解线性规划的多项式时间算法的一个非常重要的理论工具。 另一方面，将无线传感器网络的覆盖问题建模为线性规划问题会导致线性规划问题的实例规模非常大，因为在某些无线传感器网络的应用中，传感器节点的数量过大。 因此，在无线传感器网络中，解决一个基于覆盖问题的线性规划问题是非常昂贵的。</p> <p>Gupta 等人(2015)研究了连接<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">m</span></span></span></span>个无线传感器网络的 k-覆盖问题。 针对具有 k-覆盖和 连接<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">m</span></span></span></span>个无线传感器网络节点数量最少的优化配置问题，提出了一种解决方案。 该方法适用于 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.69444em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.03148em;">k</span></span></span></span> 和 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">m</span></span></span></span> 的不同取值。但该方法没有考虑网络生命周期。 他们的目标是最小化传感器节点的数量。</p> <p>同时，也有其他的研究工作通过粒子群算法来解决不同版本的无线传感器网络覆盖问题。在（Ab Aziz 等人。2009 年）的研究中，一个版本的覆盖问题已经被 PSO 解决了。文章采用粒子群优化算法，根据基于 Voronoi 图的适应度函数，寻找传感器节点的最优位置。（Ab-Aziz 等人。2009 年）和本文是版本的覆盖问题。在（Ab-Aziz 等人。2009 年），目标是如何在区域内定位传感器节点，以使覆盖百分比最大化，覆盖空洞最小化。然而，在本文的覆盖问题中，目标是如何在区域内定位传感器节点，从而使网络寿命最大化。</p> <p>在(Wang et al. 2007a，b)中，移动无线传感器网络的覆盖问题已经由粒子群优化和模拟退火解决。 该研究的目标是寻找移动传感器节点的最佳部署，以满足感知覆盖要求，最大限度地降低通信能量消耗。 和本文的主要区别在于(Wang et al. 2007a，b)假设在无线传感器网络中，传感器节点是移动的。 然而，在本文中，我们认为传感器节点是静止的。 因此，问题和解决方案是不同的。</p> <p>在(Wang 等人 2018)中，针对无线传感器网络中的能量效率和覆盖率问题，提出了一种基于粒子群优化的覆盖控制算法。 从一个角度来看，覆盖问题可以分为两类: 随机部署和计划部署。 在(王等。2018) ，随机部署的考虑，这意味着传感器节点部署在该地区随机。 然后利用粒子群优化算法对传感器节点的感知半径进行调整，使传感器节点在密集区域缩小感知半径，在稀疏区域扩大感知半径。 然而，本文提出的算法主要是针对计划部署类的覆盖问题。 在(Wang 等人 2007a，b)和(Ismail 和 Manaf 2010)中，PSO 已经解决了无线传感器网络的覆盖问题。 在这两项工作中，我们认为传感器节点在部署后可以移动。 因此，这两种工作中提出的算法都不适用于只有静态传感器节点的无线传感器网络。 然而，本文提出的算法适用于只有静态传感器节点的无线传感器网络。</p> <p>在(ZainEldin 等人 2020)中，提出了一种新的算法，以最小的传感器节点数最大化覆盖率。 该算法采用遗传算法进行求解。 定义了两个目标函数。 第一个目标是最大化区域覆盖率，第二个目标是最小化有助于最小化传感器节点之间重叠区域的传感器节点数量。仿真结果表明，该算法的性能优于其他类似算法。</p> <p>在(Kanwar 和 Kumar 2020) ，传感器部署的问题已经解决后，网络已经开始运作。 在无线传感器网络中，由于一些节点的死亡，网络被分割成若干部分。 因此，需要一种部署算法在适当的位置部署新的传感器节点，以连接网络的不同部分。 本文提出了解决这一问题的办法。 但是，这项工作没有考虑到无线传感器网络中部署问题的一般形式。 在(穆萨等人。2019 年) ，传感器部署问题已经解决的方式，平衡能源消耗的网络。实际上，它分配了传感器节点的能量消耗。 然而，与其他类似算法相比，这种方法并没有最大化无线传感器网络的生存期。</p> <p>表 1 对上述算法进行了总结和比较。 然而，以最大化网络生命周期为目标的各种目标覆盖问题(我们称之为传感器部署问题)都是 np 难问题。 因此，没有一个精确的多项式时间算法来解决这些问题。 上述算法都是近似算法，每一种算法都能得到问题的近似解。</p> <p>人们总是希望找到一个更好的近似值来解决这些问题。 为了达到这个目标，我们使用两个改进的粒子群算法来解决这些问题。 第一个版本，在第 4.2 节中给出，被称为协作 PSO 算法，可以在(den Bergh and Engelbrecht 2004; Goh et al. 2010; Li and Yao 2011)中找到。 第二个版本，在第 4.4 节中给出，使用模糊逻辑来改进协作 PSO 算法，它可以在(Liu 等人。2010; Neshat 2013; Niu et al. 2008; Valdez et al. 2011). 在(den Bergh 和 Engelbrecht 2004)中，首次引入了协作粒子群算法。 在(Goh 等人，2010 年) ，一个多目标版本的协作粒子群算法被提出。 在(李和姚 2011)中，改进了协作粒子群算法，以更好地解决大规模优化问题(多达 2000 个实值变量)。 在(Neshat 2013)中，介绍了一个改进的版本使用模糊逻辑。在(Liu 等人，2010 年) ，一个改进的粒子群算法，使用模糊逻辑，是用来解决调度工作问题。 在(牛等。2008)中，一个新的模糊建模策略被用来提供一个更好的改进协作粒子群算法使用模糊逻辑。 在(瓦尔迪兹等人 2011 年) ，粒子群算法是结合遗传算法使用模糊逻辑提供了一种进化方法。</p> <h3 id="网络生存期的上界和问题定义"><a href="#网络生存期的上界和问题定义" class="header-anchor">#</a> 网络生存期的上界和问题定义</h3> <h4 id="网络生存期的上界"><a href="#网络生存期的上界" class="header-anchor">#</a> 网络生存期的上界</h4> <p>对于无线传感器网络，可以根据网络中传感器节点的位置和能量，以数学方式确定网络生存期的上限(Chaudhary 和 Pujari，2009 年; Gu 等人，2007 年)。 我们可以利用这种方法来确定传感器的位置，从而使网络生命周期最大化。 考虑一个包含传感器节点需要监视的目标点的区域。 上限计算如下(Chaudhary 和 Pujari，2009 年; Gu 等人，2007 年) :</p> <p>假设 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">m</span></span></span></span> 个传感器节点<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>{</mo><msub><mi>S</mi><mn>1</mn></msub><mo separator="true">,</mo><msub><mi>S</mi><mn>2</mn></msub><mo separator="true">,</mo><mo>⋯</mo><mo separator="true">,</mo><msub><mi>S</mi><mi>m</mi></msub><mo>}</mo></mrow><annotation encoding="application/x-tex">\{S_1,S_2,\cdots, S_m\}</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mopen">{</span><span class="mord"><span class="mord mathit" style="margin-right:0.05764em;">S</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.05764em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.05764em;">S</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.05764em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="minner">⋯</span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.05764em;">S</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.05764em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">m</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mclose">}</span></span></span></span>被部署到覆盖 区域<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>R</mi></mrow><annotation encoding="application/x-tex">R</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.68333em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.00773em;">R</span></span></span></span>的 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">n</span></span></span></span> 个目标 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>{</mo><msub><mi>T</mi><mn>1</mn></msub><mo separator="true">,</mo><msub><mi>T</mi><mn>2</mn></msub><mo separator="true">,</mo><mo>⋯</mo><mo separator="true">,</mo><msub><mi>T</mi><mi>n</mi></msub><mo>}</mo></mrow><annotation encoding="application/x-tex">\{T_1, T_2, \cdots, T_n\}</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mopen">{</span><span class="mord"><span class="mord mathit" style="margin-right:0.13889em;">T</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.13889em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.13889em;">T</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.13889em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="minner">⋯</span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.13889em;">T</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.13889em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">n</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mclose">}</span></span></span></span>。每个传感器节点有初始能量<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>E</mi><mn>0</mn></msub></mrow><annotation encoding="application/x-tex">E_0</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit" style="margin-right:0.05764em;">E</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.05764em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">0</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span>和感应半径 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>s</mi><mi>r</mi></msub></mrow><annotation encoding="application/x-tex">s_r</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.58056em;vertical-align:-0.15em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit">s</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit" style="margin-right:0.02778em;">r</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span>。 传感器节点 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>S</mi><mi>i</mi></msub><mo separator="true">,</mo><mn>1</mn><mo>≤</mo><mi>j</mi><mo>≤</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">S_i, 1 \le j \le n</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.8777699999999999em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit" style="margin-right:0.05764em;">S</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.05764em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="mord mathrm">1</span><span class="mrel">≤</span><span class="mord mathit" style="margin-right:0.05724em;">j</span><span class="mrel">≤</span><span class="mord mathit">n</span></span></span></span>，如果 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>S</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">S_i</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit" style="margin-right:0.05764em;">S</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.05764em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span> 和 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>T</mi><mi>j</mi></msub></mrow><annotation encoding="application/x-tex">T_j</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.969438em;vertical-align:-0.286108em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit" style="margin-right:0.13889em;">T</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.13889em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit" style="margin-right:0.05724em;">j</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span> 之间的距离小于 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>s</mi><mi>r</mi></msub></mrow><annotation encoding="application/x-tex">s_r</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.58056em;vertical-align:-0.15em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit">s</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit" style="margin-right:0.02778em;">r</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span>，则称已覆盖目标 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>T</mi><mi>j</mi></msub><mo separator="true">,</mo><mn>1</mn><mo>≤</mo><mi>j</mi><mo>≤</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">T_j, 1 \le j \le n</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.969438em;vertical-align:-0.286108em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit" style="margin-right:0.13889em;">T</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.13889em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit" style="margin-right:0.05724em;">j</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="mord mathrm">1</span><span class="mrel">≤</span><span class="mord mathit" style="margin-right:0.05724em;">j</span><span class="mrel">≤</span><span class="mord mathit">n</span></span></span></span>。覆盖矩阵定义为:</p> <p><img src="https://s1.ax1x.com/2020/07/02/NLCim4.png" alt="NLCim4.png"></p> <p>其中 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>i</mi><mo>=</mo><mn>1</mn><mo separator="true">,</mo><mn>2</mn><mo separator="true">,</mo><mo>⋯</mo><mo separator="true">,</mo><mi>m</mi></mrow><annotation encoding="application/x-tex">i = 1,2, \cdots, m</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.65952em;"></span><span class="strut bottom" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit">i</span><span class="mrel">=</span><span class="mord mathrm">1</span><span class="mpunct">,</span><span class="mord mathrm">2</span><span class="mpunct">,</span><span class="minner">⋯</span><span class="mpunct">,</span><span class="mord mathit">m</span></span></span></span> 和 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>j</mi><mo>=</mo><mn>1</mn><mo separator="true">,</mo><mn>2</mn><mo separator="true">,</mo><mo>⋯</mo><mo separator="true">,</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">j = 1,2, \cdots, n</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.65952em;"></span><span class="strut bottom" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.05724em;">j</span><span class="mrel">=</span><span class="mord mathrm">1</span><span class="mpunct">,</span><span class="mord mathrm">2</span><span class="mpunct">,</span><span class="minner">⋯</span><span class="mpunct">,</span><span class="mord mathit">n</span></span></span></span>。 我们定义了<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msubsup><mrow><mi>b</mi></mrow><mi>i</mi><mrow><mi mathvariant="normal">′</mi></mrow></msubsup><mo>=</mo><mfrac><mrow><msub><mi>b</mi><mi>i</mi></msub></mrow><mrow><msub><mi>e</mi><mi>i</mi></msub></mrow></mfrac></mrow><annotation encoding="application/x-tex">{b}'_i = \frac{b_i}{e_i}</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.9011079999999999em;"></span><span class="strut bottom" style="height:1.351108em;vertical-align:-0.44999999999999996em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord textstyle uncramped"><span class="mord mathit">b</span></span><span class="vlist"><span style="top:0.258664em;margin-right:0.05em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span style="top:-0.363em;margin-right:0.05em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord scriptstyle uncramped"><span class="mord mathrm">′</span></span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mrel">=</span><span class="mord reset-textstyle textstyle uncramped"><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span><span class="mfrac"><span class="vlist"><span style="top:0.345em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord scriptstyle cramped"><span class="mord"><span class="mord mathit">e</span><span class="vlist"><span style="top:0.15em;margin-right:0.07142857142857144em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-scriptstyle scriptscriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span><span style="top:-0.22999999999999998em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle textstyle uncramped frac-line"></span></span><span style="top:-0.4149999999999999em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord scriptstyle uncramped"><span class="mord"><span class="mord mathit">b</span><span class="vlist"><span style="top:0.15em;margin-right:0.07142857142857144em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-scriptstyle scriptscriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span></span></span></span></span> 来表示电池的寿命，其中 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>b</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">b_i</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.84444em;vertical-align:-0.15em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit">b</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span> 是电池的初始功率，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>e</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">e_i</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.58056em;vertical-align:-0.15em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit">e</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span> 是节点 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>S</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">S_i</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit" style="margin-right:0.05764em;">S</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.05764em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span> 的能量消耗率。 网络生存期的上限计算如下:</p> <p><img src="https://s1.ax1x.com/2020/07/02/NLFBHe.png" alt="NLFBHe.png"></p> <p>其中 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>q</mi><mi>j</mi></msub><mo>=</mo><mi>k</mi><mo separator="true">,</mo><mi>j</mi><mo>=</mo><mn>1</mn><mo separator="true">,</mo><mn>2</mn><mo separator="true">,</mo><mo>⋯</mo><mo separator="true">,</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">q_j = k, j = 1,2, \cdots, n</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.980548em;vertical-align:-0.286108em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit" style="margin-right:0.03588em;">q</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.03588em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit" style="margin-right:0.05724em;">j</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mrel">=</span><span class="mord mathit" style="margin-right:0.03148em;">k</span><span class="mpunct">,</span><span class="mord mathit" style="margin-right:0.05724em;">j</span><span class="mrel">=</span><span class="mord mathrm">1</span><span class="mpunct">,</span><span class="mord mathrm">2</span><span class="mpunct">,</span><span class="minner">⋯</span><span class="mpunct">,</span><span class="mord mathit">n</span></span></span></span>表示 k-覆盖。 在(Chaudhary 和 Pujari，2009; Gu 等人，2007)中，已经证明了形如最大化<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>U</mi></mrow><annotation encoding="application/x-tex">U</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.68333em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.10903em;">U</span></span></span></span>的覆盖问题是一个<em>np-hard</em>问题。 本文采用两种改进的粒子群优化算法来解决这一问题。 在这些算法中，目标(适应度)函数是<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>U</mi></mrow><annotation encoding="application/x-tex">U</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.68333em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.10903em;">U</span></span></span></span>。</p> <h4 id="网络生存期问题定义"><a href="#网络生存期问题定义" class="header-anchor">#</a> 网络生存期问题定义</h4> <p>本节给出了本文所解决的各种传感器部署问题的精确定义。 考虑位于 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>u</mi><mo>×</mo><mi>v</mi></mrow><annotation encoding="application/x-tex">u \times v</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.58333em;"></span><span class="strut bottom" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="base textstyle uncramped"><span class="mord mathit">u</span><span class="mbin">×</span><span class="mord mathit" style="margin-right:0.03588em;">v</span></span></span></span> 区域的 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">n</span></span></span></span> 个目标，包括 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">m</span></span></span></span> 个传感器节点。 该算法的目标是寻找传感器节点在该区域内的位置，以满足所需的覆盖条件，使网络生命周期最大化。根据所需的覆盖条件，传感器部署问题的三个不同版本定义如下:</p> <ol><li>简单覆盖：部署传感器节点，使每个目标至少由一个传感器节点监视，网络生命周期最大。 事实上，目的是最大化 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>U</mi></mrow><annotation encoding="application/x-tex">U</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.68333em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.10903em;">U</span></span></span></span> 在公式(2)中的值，使每个目标受到至少一个传感器的监视。</li> <li>K-覆盖: 给定一组 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">n</span></span></span></span> 个目标 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>t</mi><mo>=</mo><mo>{</mo><msub><mi>T</mi><mn>1</mn></msub><mo separator="true">,</mo><msub><mi>T</mi><mn>2</mn></msub><mo separator="true">,</mo><mo>⋯</mo><mo separator="true">,</mo><msub><mi>T</mi><mi>n</mi></msub><mo>}</mo></mrow><annotation encoding="application/x-tex">t=\{T_1,T_2, \cdots, T_n \}</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit">t</span><span class="mrel">=</span><span class="mopen">{</span><span class="mord"><span class="mord mathit" style="margin-right:0.13889em;">T</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.13889em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.13889em;">T</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.13889em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="minner">⋯</span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.13889em;">T</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.13889em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">n</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mclose">}</span></span></span></span> 位于 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>u</mi><mo>×</mo><mi>v</mi></mrow><annotation encoding="application/x-tex">u \times v</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.58333em;"></span><span class="strut bottom" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="base textstyle uncramped"><span class="mord mathit">u</span><span class="mbin">×</span><span class="mord mathit" style="margin-right:0.03588em;">v</span></span></span></span> 区域，包括 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">m</span></span></span></span> 个传感器节点 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>S</mi><mo>=</mo><mo>{</mo><msub><mi>S</mi><mn>1</mn></msub><mo separator="true">,</mo><msub><mi>S</mi><mn>2</mn></msub><mo separator="true">,</mo><mo>⋯</mo><mo separator="true">,</mo><msub><mi>S</mi><mi>m</mi></msub><mo>}</mo></mrow><annotation encoding="application/x-tex">S=\{S_1,S_2, \cdots , S_m\}</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.05764em;">S</span><span class="mrel">=</span><span class="mopen">{</span><span class="mord"><span class="mord mathit" style="margin-right:0.05764em;">S</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.05764em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.05764em;">S</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.05764em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="minner">⋯</span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.05764em;">S</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.05764em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">m</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mclose">}</span></span></span></span>，目的是将传感器节点放置在该区域，使每个目标至少受到 k 个传感器节点的监视，并且最大化公式(2)中的<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>U</mi></mrow><annotation encoding="application/x-tex">U</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.68333em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.10903em;">U</span></span></span></span>。</li> <li>Q-覆盖: 给定一组 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">n</span></span></span></span> 个目标 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>t</mi><mo>=</mo><mo>{</mo><msub><mi>T</mi><mn>1</mn></msub><mo separator="true">,</mo><msub><mi>T</mi><mn>2</mn></msub><mo separator="true">,</mo><mo>⋯</mo><mo separator="true">,</mo><msub><mi>T</mi><mi>n</mi></msub><mo>}</mo></mrow><annotation encoding="application/x-tex">t = \{T_1,T_2, \cdots,T_n\}</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit">t</span><span class="mrel">=</span><span class="mopen">{</span><span class="mord"><span class="mord mathit" style="margin-right:0.13889em;">T</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.13889em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.13889em;">T</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.13889em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="minner">⋯</span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.13889em;">T</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.13889em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">n</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mclose">}</span></span></span></span> 位于一个<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>u</mi><mo>×</mo><mi>v</mi></mrow><annotation encoding="application/x-tex">u \times v</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.58333em;"></span><span class="strut bottom" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="base textstyle uncramped"><span class="mord mathit">u</span><span class="mbin">×</span><span class="mord mathit" style="margin-right:0.03588em;">v</span></span></span></span> 区域，其中包括 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">m</span></span></span></span> 个传感器节点 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>S</mi><mo>=</mo><mo>{</mo><msub><mi>S</mi><mn>1</mn></msub><mo separator="true">,</mo><msub><mi>S</mi><mn>2</mn></msub><mo separator="true">,</mo><mo>⋯</mo><mo separator="true">,</mo><msub><mi>S</mi><mi>m</mi></msub><mo>}</mo></mrow><annotation encoding="application/x-tex">S=\{S_1,S_2, \cdots , S_m\}</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.05764em;">S</span><span class="mrel">=</span><span class="mopen">{</span><span class="mord"><span class="mord mathit" style="margin-right:0.05764em;">S</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.05764em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.05764em;">S</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.05764em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="minner">⋯</span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.05764em;">S</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.05764em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">m</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mclose">}</span></span></span></span> 和一个向量 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>q</mi><mo>=</mo><mo>{</mo><msub><mi>q</mi><mn>1</mn></msub><mo separator="true">,</mo><msub><mi>q</mi><mn>2</mn></msub><mo separator="true">,</mo><mo>⋯</mo><mo separator="true">,</mo><msub><mi>q</mi><mi>n</mi></msub><mo>}</mo></mrow><annotation encoding="application/x-tex">q = \{q_1, q_2, \cdots, q_n\}</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.03588em;">q</span><span class="mrel">=</span><span class="mopen">{</span><span class="mord"><span class="mord mathit" style="margin-right:0.03588em;">q</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.03588em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.03588em;">q</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.03588em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="minner">⋯</span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.03588em;">q</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.03588em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">n</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mclose">}</span></span></span></span>，目的是布置节点，使每个目标 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>T</mi><mi>j</mi></msub><mo separator="true">,</mo><mn>1</mn><mo>≤</mo><mi>j</mi><mo>≤</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">T_j, 1 \le j \le n</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.969438em;vertical-align:-0.286108em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit" style="margin-right:0.13889em;">T</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.13889em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit" style="margin-right:0.05724em;">j</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="mord mathrm">1</span><span class="mrel">≤</span><span class="mord mathit" style="margin-right:0.05724em;">j</span><span class="mrel">≤</span><span class="mord mathit">n</span></span></span></span>，至少被 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>q</mi><mi>j</mi></msub></mrow><annotation encoding="application/x-tex">q_j</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.716668em;vertical-align:-0.286108em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit" style="margin-right:0.03588em;">q</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.03588em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit" style="margin-right:0.05724em;">j</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span> 传感器节点覆盖，并在公式(2)中使 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>U</mi></mrow><annotation encoding="application/x-tex">U</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.68333em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.10903em;">U</span></span></span></span>最大化。</li></ol> <h3 id="本文的提出的粒子群优化方法"><a href="#本文的提出的粒子群优化方法" class="header-anchor">#</a> 本文的提出的粒子群优化方法</h3> <p>在这一部分中，我们描述了所提出的解决无线传感器网络中传感器部署问题的算法。 在本文中，我们认为传感器节点的位置可以在它们被部署之前被确定。 本文提出的算法的任务是在传感器节点部署前确定其在区域内的位置。 首先，对粒子群优化算法进行了概述。</p> <h4 id="粒子群优化算法概述"><a href="#粒子群优化算法概述" class="header-anchor">#</a> 粒子群优化算法概述</h4> <p>粒子群优化（PSO）是一个庞大的群体智能方法(Mavrovouniotis et al)用于解决优化问题。PSO 首先由 Eberhart 和 Kennedy（1995）提出。这种方法的灵感来源于成群迁徙的动物的自然生活。由于群体中的每个成员都会根据群体来调整自己的位置和速度，从而减少了个体在寻找食物、住所等方面的行为影响。<br>
粒子群优化算法由一群粒子组成。每个粒子都是问题的完整解决方案。每一个粒子群都有自己的速度，这种速度会随着它在搜索空间中的移动而变化。此外，每个粒子都有一个内存，它在其中保存了它曾经处于的最佳位置。每个粒子都朝着自己的最佳位置以及整个群的最佳位置移动。为此，每个粒子的速度向量和位置向量都会根据它们所处的最佳位置和整个群中的最佳位置进行更新。</p> <h4 id="合作粒子群算法-cpso"><a href="#合作粒子群算法-cpso" class="header-anchor">#</a> 合作粒子群算法(CPSO)</h4> <h4 id="利用-cpso-解决传感器部署问题"><a href="#利用-cpso-解决传感器部署问题" class="header-anchor">#</a> 利用 CPSO 解决传感器部署问题</h4> <p>提出了一种基于 cpso 的传感器部署算法，该算法包括粒子编码方案、粒子初始化、适应度函数的确定、速度和位置更新阶段以及终止准则。</p> <p>(1) 粒子编码方式</p> <p>利用标准粒子群算法解决传感器部署问题，假设每个粒子都是问题的可行解。 假设我们有一个拥有 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">m</span></span></span></span> 个节点的网络和一个规模为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>u</mi><mo>×</mo><mi>v</mi></mrow><annotation encoding="application/x-tex">u \times v</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.58333em;"></span><span class="strut bottom" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="base textstyle uncramped"><span class="mord mathit">u</span><span class="mbin">×</span><span class="mord mathit" style="margin-right:0.03588em;">v</span></span></span></span> 的二维传感器部署区域。 要部署每个传感器节点，需要两个维度 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">x</span></span></span></span> 和 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>y</mi></mrow><annotation encoding="application/x-tex">y</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.03588em;">y</span></span></span></span>。 因此，问题的每个可行解都是一个粒子，它等于 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">m</span></span></span></span> 对 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>{</mo><mo>(</mo><msub><mi>x</mi><mn>1</mn></msub><mo separator="true">,</mo><msub><mi>y</mi><mn>1</mn></msub><mo>)</mo><mo separator="true">,</mo><mo>(</mo><msub><mi>x</mi><mn>2</mn></msub><mo separator="true">,</mo><msub><mi>y</mi><mn>2</mn></msub><mo>)</mo><mo separator="true">,</mo><mo>⋯</mo><mo separator="true">,</mo><mo>(</mo><msub><mi>x</mi><mi>m</mi></msub><mo separator="true">,</mo><msub><mi>y</mi><mi>m</mi></msub><mo>)</mo><mo>}</mo></mrow><annotation encoding="application/x-tex">\{(x_1,y_1),(x_2,y_2), \cdots ,(x_m,y_m)\}</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mopen">{</span><span class="mopen">(</span><span class="mord"><span class="mord mathit">x</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.03588em;">y</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.03588em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mclose">)</span><span class="mpunct">,</span><span class="mopen">(</span><span class="mord"><span class="mord mathit">x</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.03588em;">y</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.03588em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mclose">)</span><span class="mpunct">,</span><span class="minner">⋯</span><span class="mpunct">,</span><span class="mopen">(</span><span class="mord"><span class="mord mathit">x</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">m</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.03588em;">y</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.03588em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">m</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mclose">)</span><span class="mclose">}</span></span></span></span>，其中<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>0</mn><mo>≤</mo><msub><mi>x</mi><mi>i</mi></msub><mo>≤</mo><mi>u</mi></mrow><annotation encoding="application/x-tex">0 \le x_i \le u</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.64444em;"></span><span class="strut bottom" style="height:0.79444em;vertical-align:-0.15em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">0</span><span class="mrel">≤</span><span class="mord"><span class="mord mathit">x</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mrel">≤</span><span class="mord mathit">u</span></span></span></span>，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>0</mn><mo>≤</mo><msub><mi>y</mi><mi>i</mi></msub><mo>≤</mo><mi>v</mi></mrow><annotation encoding="application/x-tex">0 \le y_i \le v</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.64444em;"></span><span class="strut bottom" style="height:0.8388800000000001em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">0</span><span class="mrel">≤</span><span class="mord"><span class="mord mathit" style="margin-right:0.03588em;">y</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.03588em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mrel">≤</span><span class="mord mathit" style="margin-right:0.03588em;">v</span></span></span></span>对于每个 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>i</mi><mo>∈</mo><mo>{</mo><mn>1</mn><mo separator="true">,</mo><mn>2</mn><mo separator="true">,</mo><mo>⋯</mo><mo separator="true">,</mo><mi>m</mi><mo>}</mo></mrow><annotation encoding="application/x-tex">i \in \{1,2, \cdots ,m \}</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit">i</span><span class="mrel">∈</span><span class="mopen">{</span><span class="mord mathrm">1</span><span class="mpunct">,</span><span class="mord mathrm">2</span><span class="mpunct">,</span><span class="minner">⋯</span><span class="mpunct">,</span><span class="mord mathit">m</span><span class="mclose">}</span></span></span></span>，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>(</mo><msub><mi>x</mi><mi>i</mi></msub><mo separator="true">,</mo><msub><mi>y</mi><mi>i</mi></msub><mo>)</mo></mrow><annotation encoding="application/x-tex">(x_i,y_i)</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mopen">(</span><span class="mord"><span class="mord mathit">x</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.03588em;">y</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.03588em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mclose">)</span></span></span></span>是第<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.65952em;"></span><span class="strut bottom" style="height:0.65952em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">i</span></span></span></span>个传感器节点的位置。每个群体都是一个粒子的集合; 这意味着每个群体都是问题的可行解决方案的集合。 因此，在使用标准粒子群算法解决传感器部署问题时，一个大小为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>l</mi></mrow><annotation encoding="application/x-tex">l</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.69444em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.01968em;">l</span></span></span></span> 的群确实是该区域传感器节点不同部署的集合。</p> <div class="custom-block tip"><p class="custom-block-title">思考</p> <p>这里的<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>l</mi></mrow><annotation encoding="application/x-tex">l</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.69444em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.01968em;">l</span></span></span></span>代表的是粒子群的粒子个数，按照上述表示方式，对于<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">m</span></span></span></span>个节点的网络，粒子群的单个粒子的维度应该是<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>2</mn><mi>m</mi></mrow><annotation encoding="application/x-tex">2m</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.64444em;"></span><span class="strut bottom" style="height:0.64444em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">2</span><span class="mord mathit">m</span></span></span></span>，一个粒子就能代表一种<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">m</span></span></span></span>个传感器的分布。</p></div> <p>为了解决使用 CPSO 的传感器部署问题，我们假设我们有<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">m</span></span></span></span>个一维群( <mark>实际上是二维群，因为是一对<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>(</mo><msub><mi>x</mi><mi>i</mi></msub><mo separator="true">,</mo><msub><mi>y</mi><mi>i</mi></msub><mo>)</mo></mrow><annotation encoding="application/x-tex">(x_i,y_i)</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mopen">(</span><span class="mord"><span class="mord mathit">x</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.03588em;">y</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.03588em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mclose">)</span></span></span></span></mark> )，其中每个群是<strong>一个</strong>传感器节点在该地区的不同部署的集合。 通过这种方式，传感器部署问题不再依赖维度( <mark>因为维度靠群数量进行替换了，一个群代表一个传感器，维度都是一维，准确的说是二维</mark> ); 因此，每个群体被认为是一维的，因为每两个传感器的部署彼此独立（ <mark>严格说来相互之间并不独立，因为传感器区域尽量不要重合，尤其是简单部署问题。当然，每个传感器都可以随便放是真的</mark> ）。</p> <p>因此，我们有<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">m</span></span></span></span>个大小为<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>l</mi></mrow><annotation encoding="application/x-tex">l</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.69444em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.01968em;">l</span></span></span></span>的群。该算法的主要目的是在区域内寻找传感器节点的部署使得网络生命周期最长。该算法可以找到问题的最优解或近似最优解。 如果将两个不同的传感器节点部署在同一位置，从而减少了网络的生存时间，该算法将改变节点的位置。每个群 i (1≤ i ≤ m)由 l 对组成，表示为 li = x1，y1，x2，y2，... ，xl，yl，其中每个对 xj，yj 是区域内 i-th 节点的位置，对于每个 j ∈{1,2，... ，l } ，0≤ xj ≤ u 和 0≤ yj ≤ v。 在本算法中，上下文向量由 m 对组成: x1，y1，x2，y2，... ，xm，ym，其中 xi，yi 是第 i 传感器节点的位置，对每个 i ∈{1,2，... ，m } ，0≤ xi ≤ u 和 0≤ yi ≤ v。</p> <div class="custom-block warning"><p class="custom-block-title">理解</p> <p>相当于进行了维度对调，普通的粒子群算法是<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>l</mi></mrow><annotation encoding="application/x-tex">l</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.69444em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.01968em;">l</span></span></span></span>个<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>2</mn><mi>m</mi></mrow><annotation encoding="application/x-tex">2m</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.64444em;"></span><span class="strut bottom" style="height:0.64444em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">2</span><span class="mord mathit">m</span></span></span></span>维度的粒子，CPSO 则用多个群（<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">m</span></span></span></span>个粒子群），每个粒子群由<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>l</mi></mrow><annotation encoding="application/x-tex">l</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.69444em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.01968em;">l</span></span></span></span>个粒子组成，每个粒子都是一维（实际是二维）。</p></div> <p>传感器节点的部署必须满足传感器部署问题的要求条件。 每个群体的任务是部署一个传感器节点，以满足部署问题的条件。 用这种方法，我们不是解 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">m</span></span></span></span> 维问题，而是解 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">m</span></span></span></span> 个一维问题。 在 CPSO 中，上下文向量将在每次迭代中用 <em>Gbest</em>( <mark>全局最优，就是 CPSO 中的上下文环境向量，由<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">m</span></span></span></span>个粒子群中最优的那个粒子位置合并得来</mark> ) 填充。 在算法的每一次迭代中，<em>Gbest</em> 是传感器部署问题的一个可行解。 当一个 <em>Gbest</em> 元素被一个粒子代替时，我们检查这个解决方案是否提供了传感器部署问题所需的条件。 如果不是，那个 <em>Gbest</em> 元素将被另一个适应值大于该群中其他粒子的粒子所取代（ <mark>为什么是被适应度更大的取代，我们不就是为了找最大化适应度函数<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>U</mi></mrow><annotation encoding="application/x-tex">U</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.68333em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.10903em;">U</span></span></span></span>么？那不应该一开始就用最大的适应度粒子🐶，另外 CPSO 中是一个维度一个维度进行计算，万一群里面的<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>l</mi></mrow><annotation encoding="application/x-tex">l</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.69444em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.01968em;">l</span></span></span></span>个粒子都没有符合条件，肿么办？</mark> ）。 实际上，我们的算法始终保持 <em>Gbest</em> 为问题的一个可行解，这意味着 <em>Gbest</em> 满足传感器部署问题的要求条件。</p> <p>(2)粒子的初始化</p> <p>每个群体中的每个粒子都可以被识别为一对<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>(</mo><mi>x</mi><mo separator="true">,</mo><mi>y</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">(x,y)</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mopen">(</span><span class="mord mathit">x</span><span class="mpunct">,</span><span class="mord mathit" style="margin-right:0.03588em;">y</span><span class="mclose">)</span></span></span></span>。为了初始化粒子，对每个粒子生成两个随机数 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">x</span></span></span></span> 和 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>y</mi></mrow><annotation encoding="application/x-tex">y</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.03588em;">y</span></span></span></span>，使得 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>0</mn><mo>≤</mo><mi>x</mi><mo>≤</mo><mi>u</mi></mrow><annotation encoding="application/x-tex">0 \le x \le u</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.64444em;"></span><span class="strut bottom" style="height:0.78041em;vertical-align:-0.13597em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">0</span><span class="mrel">≤</span><span class="mord mathit">x</span><span class="mrel">≤</span><span class="mord mathit">u</span></span></span></span> 和 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>0</mn><mo>≤</mo><mi>y</mi><mo>≤</mo><mi>v</mi></mrow><annotation encoding="application/x-tex">0 \le y \le v</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.64444em;"></span><span class="strut bottom" style="height:0.8388800000000001em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">0</span><span class="mrel">≤</span><span class="mord mathit" style="margin-right:0.03588em;">y</span><span class="mrel">≤</span><span class="mord mathit" style="margin-right:0.03588em;">v</span></span></span></span>。</p> <p>(3)适应度函数<br>
这里的主要目标是确定传感器节点的位置，以便满足所需的条件并使网络寿命最大化。因此，适应度函数是公式(2)中的 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>U</mi></mrow><annotation encoding="application/x-tex">U</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.68333em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.10903em;">U</span></span></span></span>，它实际上就是网络生存期。</p> <p>(4)速度和位置更新<br>
每个粒子的速度和位置在每次迭代中都使用公式(3)和(4)进行更新。然而，这些方程中加减运算的代数步骤可能会导致粒子的新位置超出范围（不在<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>u</mi><mo>×</mo><mi>v</mi></mrow><annotation encoding="application/x-tex">u\times v</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.58333em;"></span><span class="strut bottom" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="base textstyle uncramped"><span class="mord mathit">u</span><span class="mbin">×</span><span class="mord mathit" style="margin-right:0.03588em;">v</span></span></span></span>范围内）。因此，所提出的算法处理粒子的位置，要能使它们落在期望的范围内。以下三个规则处理粒子<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>(</mo><mi>x</mi><mo separator="true">,</mo><mi>y</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">(x,y)</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mopen">(</span><span class="mord mathit">x</span><span class="mpunct">,</span><span class="mord mathit" style="margin-right:0.03588em;">y</span><span class="mclose">)</span></span></span></span>的这些场景：</p> <ol><li>如果 x 或 y 是负数，用一个新的随机数替换它。</li> <li>如果<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>x</mi><mo>&gt;</mo><mi>u</mi></mrow><annotation encoding="application/x-tex">x&gt;u</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.5391em;"></span><span class="strut bottom" style="height:0.5782em;vertical-align:-0.0391em;"></span><span class="base textstyle uncramped"><span class="mord mathit">x</span><span class="mrel">&gt;</span><span class="mord mathit">u</span></span></span></span>，那么<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>x</mi><mo>=</mo><mi>u</mi></mrow><annotation encoding="application/x-tex">x=u</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">x</span><span class="mrel">=</span><span class="mord mathit">u</span></span></span></span>。</li> <li>如果<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>y</mi><mo>&gt;</mo><mi>v</mi></mrow><annotation encoding="application/x-tex">y&gt;v</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.5391em;"></span><span class="strut bottom" style="height:0.7335400000000001em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.03588em;">y</span><span class="mrel">&gt;</span><span class="mord mathit" style="margin-right:0.03588em;">v</span></span></span></span>，那么<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>y</mi><mo>=</mo><mi>v</mi></mrow><annotation encoding="application/x-tex">y=v</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.03588em;">y</span><span class="mrel">=</span><span class="mord mathit" style="margin-right:0.03588em;">v</span></span></span></span>。</li></ol> <p>在生成新的位置后，第<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.65952em;"></span><span class="strut bottom" style="height:0.65952em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">i</span></span></span></span>个群（<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>1</mn><mo>≤</mo><mi>i</mi><mo>≤</mo><mi>m</mi></mrow><annotation encoding="application/x-tex">1\le i\le m</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.65952em;"></span><span class="strut bottom" style="height:0.79549em;vertical-align:-0.13597em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">1</span><span class="mrel">≤</span><span class="mord mathit">i</span><span class="mrel">≤</span><span class="mord mathit">m</span></span></span></span>）中的每个粒子被上下文向量中的第 i 个元素替换。然后，利用适应度函数计算上下文向量。现在，只要它的当前适应值比它的 <em>Pbest</em> 适应值好，那么每个粒子的 <em>Pbest</em> 就会被替换掉。然后，根据粒子适应度函数的值对 <em>Gbest</em> 进行更新。</p> <div class="custom-block tip"><p class="custom-block-title">理解</p> <p>也就是说粒子的 <em>Pbest</em> 的是不考虑覆盖条件，只考虑适应度值函数的。但是 <em>Gbest</em> 必须考虑，所以下面着重开始说 <em>Gbest</em> 的情况。</p></div> <p>更新 <em>Gbest</em> 的过程必须考虑所需的覆盖条件。事实上，它必须更新 <em>Gbest</em>，使之成为解决问题的可行方案。换句话说，必须更新 <em>Gbest</em>，使其满足所需的覆盖条件。为了实现这一目标，在将一个粒子放入 <em>Gbest</em> 的每个步骤中，都会检查所需的覆盖条件；如果不满足这些条件，则将另一个满足所需覆盖条件的粒子放入 <em>Gbest</em>。然后，上下文向量将填充 <em>Gbest</em>。</p> <div class="custom-block warning"><p class="custom-block-title">理解</p> <p>说白了，就是 <em>Gbest</em> 必须满足覆盖条件（比如必须每个目标都要被覆盖到，或者第<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.69444em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.03148em;">k</span></span></span></span>个目标被<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>q</mi><mi>k</mi></msub></mrow><annotation encoding="application/x-tex">q_k</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit" style="margin-right:0.03588em;">q</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.03588em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit" style="margin-right:0.03148em;">k</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span>个传感器覆盖呀等等），如果放入的粒子不满足条件，则换一个（那这样每个粒子群自身的<em>Gbest</em>不就没有意义了么？</p></div> <p>(5) 终止条件</p> <p>迭代更新速度和位置，直到满足终止条件。在我们的算法中，终止条件是预先定义好的迭代次数。Gbest 表示节点的最终部署情况。CPSO 算法的伪码如下所示。</p> <div class="language- extra-class"><pre class="language-text"><code>输入：l, m, u, v
对于m个粒子群，初始化中每个群中l个粒子
没有达到最大迭代次数则进行循环{
  对于每个群进行循环{
    对于每个群中的粒子进行循环{
      更新上下文环境向量
      计算上下文环境向量的网络生存期，并把它放到UCurrent中
      如果UCurrent&gt;Pbest{
        将当前值设置为该粒子的新Pbest
      }
    }
  }
  在所有粒子中选择适应度值最佳的粒子作为Gbest，使其满足传感器部署问题所需的条件
  用Gbest填充上下文向量
  对于每个粒子进行循环{
    根据速度更新方程（3）计算粒子速度
    根据位置更新方程（4）更新粒子位置
  }
}
输出：Gbest
</code></pre></div><div class="custom-block danger"><p class="custom-block-title">疑问</p> <p>每个群自己的 Gbest 提供出来作为环境向量，那万一各个群拼起来的环境向量不符合约束条件呢？（比如 K 约束），那么这时候应该用哪种策略进行修正？另外初始的 Gbest 要怎么获得，因为必须要满足约束条件。</p></div> <p><strong>实例 1</strong>：考虑 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>K</mi><mo>=</mo><mn>3</mn></mrow><annotation encoding="application/x-tex">K=3</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.68333em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.07153em;">K</span><span class="mrel">=</span><span class="mord mathrm">3</span></span></span></span> 的 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>K</mi></mrow><annotation encoding="application/x-tex">K</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.68333em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.07153em;">K</span></span></span></span> 覆盖问题，共有 6 个传感器节点，2 个目标的无线传感器网络，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>m</mi><mo>=</mo><mn>6</mn></mrow><annotation encoding="application/x-tex">m=6</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.64444em;"></span><span class="strut bottom" style="height:0.64444em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">m</span><span class="mrel">=</span><span class="mord mathrm">6</span></span></span></span>，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>n</mi><mo>=</mo><mn>2</mn></mrow><annotation encoding="application/x-tex">n=2</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.64444em;"></span><span class="strut bottom" style="height:0.64444em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">n</span><span class="mrel">=</span><span class="mord mathrm">2</span></span></span></span>，CPSO 中每个群有 20 个粒子，即 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>l</mi><mo>=</mo><mn>2</mn><mn>0</mn></mrow><annotation encoding="application/x-tex">l=20</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.69444em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.01968em;">l</span><span class="mrel">=</span><span class="mord mathrm">2</span><span class="mord mathrm">0</span></span></span></span>。在这个例子中，目标是在区域中部署传感器节点，使得每个目标被至少 3 个传感器节点覆盖，并且实现最大的网络生存期。用粒子群算法解决这个问题的模型是将每个粒子作为传感器节点的一个部署。因此每个粒子都可以用<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>p</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">p_i</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit">p</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span>表示，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>p</mi><mi>i</mi></msub><mo>=</mo><mo>{</mo><mo>(</mo><msub><mi>x</mi><mn>1</mn></msub><mo separator="true">,</mo><msub><mi>y</mi><mn>1</mn></msub><mo>)</mo><mo separator="true">,</mo><mo>(</mo><msub><mi>x</mi><mn>2</mn></msub><mo separator="true">,</mo><msub><mi>y</mi><mn>2</mn></msub><mo>)</mo><mo separator="true">,</mo><mo>⋯</mo><mo separator="true">,</mo><mo>(</mo><msub><mi>x</mi><mn>6</mn></msub><mo separator="true">,</mo><msub><mi>y</mi><mn>6</mn></msub><mo>)</mo><mo>}</mo></mrow><annotation encoding="application/x-tex">p_i=\{(x_1,y_1),(x_2,y_2),\cdots,(x_6,y_6)\}</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit">p</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mrel">=</span><span class="mopen">{</span><span class="mopen">(</span><span class="mord"><span class="mord mathit">x</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.03588em;">y</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.03588em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mclose">)</span><span class="mpunct">,</span><span class="mopen">(</span><span class="mord"><span class="mord mathit">x</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.03588em;">y</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.03588em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mclose">)</span><span class="mpunct">,</span><span class="minner">⋯</span><span class="mpunct">,</span><span class="mopen">(</span><span class="mord"><span class="mord mathit">x</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">6</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.03588em;">y</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.03588em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">6</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mclose">)</span><span class="mclose">}</span></span></span></span>，其中<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>1</mn><mo>≤</mo><mi>i</mi><mo>≤</mo><mn>2</mn><mn>0</mn></mrow><annotation encoding="application/x-tex">1\le i \le 20</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.65952em;"></span><span class="strut bottom" style="height:0.79549em;vertical-align:-0.13597em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">1</span><span class="mrel">≤</span><span class="mord mathit">i</span><span class="mrel">≤</span><span class="mord mathrm">2</span><span class="mord mathrm">0</span></span></span></span>，因此，群集合可以用<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>L</mi><mo>=</mo><mo>{</mo><msub><mi>p</mi><mn>1</mn></msub><mo separator="true">,</mo><msub><mi>p</mi><mn>2</mn></msub><mo separator="true">,</mo><mo>⋯</mo><mo separator="true">,</mo><msub><mi>p</mi><mrow><mn>2</mn><mn>0</mn></mrow></msub><mo>}</mo></mrow><annotation encoding="application/x-tex">L=\{p_1,p_2,\cdots, p_{20}\}</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit">L</span><span class="mrel">=</span><span class="mopen">{</span><span class="mord"><span class="mord mathit">p</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathit">p</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="minner">⋯</span><span class="mpunct">,</span><span class="mord"><span class="mord mathit">p</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord scriptstyle cramped"><span class="mord mathrm">2</span><span class="mord mathrm">0</span></span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mclose">}</span></span></span></span>表示。</p> <p>为了用 CPSO 来解决这个问题，我们假设我们有 6 个一维群，其中每个群都是该区域传感器节点不同部署的集合。因此，我们有 6 个群<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>δ</mi><mn>1</mn></msub><mo separator="true">,</mo><mi>d</mi><mi>e</mi><mi>l</mi><mi>t</mi><msub><mi>a</mi><mn>2</mn></msub><mo separator="true">,</mo><mo>⋯</mo><mo separator="true">,</mo><mi>d</mi><mi>e</mi><mi>l</mi><mi>t</mi><msub><mi>a</mi><mn>6</mn></msub></mrow><annotation encoding="application/x-tex">\delta_1,delta_2,\cdots,delta_6</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit" style="margin-right:0.03785em;">δ</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.03785em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="mord mathit">d</span><span class="mord mathit">e</span><span class="mord mathit" style="margin-right:0.01968em;">l</span><span class="mord mathit">t</span><span class="mord"><span class="mord mathit">a</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="minner">⋯</span><span class="mpunct">,</span><span class="mord mathit">d</span><span class="mord mathit">e</span><span class="mord mathit" style="margin-right:0.01968em;">l</span><span class="mord mathit">t</span><span class="mord"><span class="mord mathit">a</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">6</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span>，并且 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>δ</mi><mi>j</mi></msub></mrow><annotation encoding="application/x-tex">\delta_j</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.980548em;vertical-align:-0.286108em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit" style="margin-right:0.03785em;">δ</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.03785em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit" style="margin-right:0.05724em;">j</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span>是该区域传感器节点 j 的不同部署的集合。现在在这个问题示例上实现图 1 所示算法的步骤 3 到 20。</p> <p>在下一个例子中，给出了算法提供的最终部署。</p> <h4 id="用模糊逻辑改进-cpso-cpso-ufuzzy"><a href="#用模糊逻辑改进-cpso-cpso-ufuzzy" class="header-anchor">#</a> 用模糊逻辑改进 CPSO（CPSO_ufuzzy）</h4> <p>我们现在提出了一种改进的合作粒子群算法（CPSO_fuzzy）。公式(3)中用<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>c</mi><mn>1</mn></msub></mrow><annotation encoding="application/x-tex">c_1</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.58056em;vertical-align:-0.15em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit">c</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span>和<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>c</mi><mn>2</mn></msub></mrow><annotation encoding="application/x-tex">c_2</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.58056em;vertical-align:-0.15em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit">c</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span>表示的恒定加速度系数将每个粒子引导到<em>Pbest</em>和<em>Gbest</em>位置。这意味着随着迭代次数的增加，这些系数将导致粒子向<em>Pbest</em>和<em>Gbest</em>位置移动。这些系数很大会使粒子突然向目标区域移动（尽管最佳解不一定在该区域），而较低的值允许粒子远离目标区域漫游。最近，对粒子群算法（试错法）的检验表明，如果加速度系数等于 2，则会获得更好的结果。然而，这并不总是正确的（Ratnaweera 等人。2004 年）。有时在问题的搜索空间中，全局搜索优于局部搜索，反之亦然。在迭代过程中，如果加速度系数以智能的方式变化并适应当前条件，则可以获得更好的结果。</p> <h2 id="cpso-算法"><a href="#cpso-算法" class="header-anchor">#</a> CPSO 算法</h2> <blockquote><p>粒子群优化(PSO)是一种随机的，基于种群的优化技术，可以应用于广泛的问题，包括神经网络的训练。 本文提出了一种改进的传统粒子群优化算法，称为合作粒子群优化器，或 CPSO，利用合作行为显着提高了原算法的性能。 这是通过使用多个群优化解决方案向量的不同组成部分合作实现的。 新的粒子群算法在几个基准优化问题上的应用表明，与传统粒子群算法相比，性能有了明显的改善。</p></blockquote> <h3 id="原始-pso-算法和名词解释"><a href="#原始-pso-算法和名词解释" class="header-anchor">#</a> 原始 PSO 算法和名词解释</h3> <p><img src="https://s1.ax1x.com/2020/07/02/NLyeeI.png" alt="NLyeeI.png"></p> <div class="custom-block tip"><p class="custom-block-title">名词解释</p> <p>标准粒子群算法伪代码中，对于一个粒子群中的第<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.65952em;"></span><span class="strut bottom" style="height:0.65952em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">i</span></span></span></span>个粒子，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>P</mi><mo>:</mo><mi>P</mi><mi mathvariant="normal">.</mi><msub><mi>x</mi><mi>i</mi></msub><mo separator="true">,</mo><mi>P</mi><mi mathvariant="normal">.</mi><msub><mi>v</mi><mi>i</mi></msub><mo separator="true">,</mo><mi>P</mi><mi mathvariant="normal">.</mi><msub><mi>y</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">P:P.x_i, P.v_i, P.y_i</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.8777699999999999em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.13889em;">P</span><span class="mrel">:</span><span class="mord mathit" style="margin-right:0.13889em;">P</span><span class="mord mathrm">.</span><span class="mord"><span class="mord mathit">x</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="mord mathit" style="margin-right:0.13889em;">P</span><span class="mord mathrm">.</span><span class="mord"><span class="mord mathit" style="margin-right:0.03588em;">v</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.03588em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="mord mathit" style="margin-right:0.13889em;">P</span><span class="mord mathrm">.</span><span class="mord"><span class="mord mathit" style="margin-right:0.03588em;">y</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.03588em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span>分别代表粒子的位置，速度和局部最优位置，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>P</mi><mi mathvariant="normal">.</mi><mover accent="true"><mrow><mi>y</mi></mrow><mo>^</mo></mover></mrow><annotation encoding="application/x-tex">P.\hat{y}</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.13889em;">P</span><span class="mord mathrm">.</span><span class="mord accent"><span class="vlist"><span style="top:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="mord textstyle cramped"><span class="mord mathit" style="margin-right:0.03588em;">y</span></span></span><span style="top:0em;margin-left:0.11112em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="accent-body"><span>^</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span>代表全局最优位置，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>f</mi></mrow><annotation encoding="application/x-tex">f</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.10764em;">f</span></span></span></span>代表适应度函数。</p></div> <h3 id="cpso-sk-算法"><a href="#cpso-sk-算法" class="header-anchor">#</a> CPSO-SK 算法</h3> <p>原始的粒子群算法使用 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">n</span></span></span></span> 维向量的种群(一个粒子是<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">n</span></span></span></span>维向量，代表一个解)。事实上，可以把<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">n</span></span></span></span>维向量分成 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">n</span></span></span></span> 个一维向量，对每个一维向量使用粒子群进行优化，这时每个粒子群就代表原问题的一个维度。 每个粒子群都试图优化最优解的一个组成部分（维度），本质上是一维优化问题。 这种分解类似于松弛法中使用的分解。</p> <p>这种这种方法的一个复杂之处在于，要最小化的函数（目标函数）<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>f</mi></mrow><annotation encoding="application/x-tex">f</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.10764em;">f</span></span></span></span> 需要一个 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">n</span></span></span></span> 维向量作为输入。 如果每个群体只代表搜索空间的一个维度，那么显然不可能直接计算每个粒子群的个体适应度（因为只有一个维度，所以没法用适应度函数算）。这时我们需要提供一个合适的上下文环境向量（<strong>context vector</strong>），在这个上下文环境中就可以评估每个粒子群中的个体。构造这样一个上下文向量最简单的方案是从每一个群中取出全局最佳粒子，并将它们连接起来形成这样一个 n 维向量。 为了计算粒子群<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.65952em;"></span><span class="strut bottom" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.05724em;">j</span></span></span></span>中所有粒子的适应度，上下文环境向量中的其他<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">n-1</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.64444em;"></span><span class="strut bottom" style="height:0.72777em;vertical-align:-0.08333em;"></span><span class="base textstyle uncramped"><span class="mord mathit">n</span><span class="mbin">−</span><span class="mord mathrm">1</span></span></span></span>个分量保持不变(其值设置为来自其他<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">n-1</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.64444em;"></span><span class="strut bottom" style="height:0.72777em;vertical-align:-0.08333em;"></span><span class="base textstyle uncramped"><span class="mord mathit">n</span><span class="mbin">−</span><span class="mord mathrm">1</span></span></span></span>粒子群的全局最优粒子)，而上下文环境向量的 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.65952em;"></span><span class="strut bottom" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.05724em;">j</span></span></span></span> 分量依次由来自 第<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.65952em;"></span><span class="strut bottom" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.05724em;">j</span></span></span></span>个粒子群的每个粒子代替。</p> <p><img src="https://s1.ax1x.com/2020/07/02/NLsqWF.png" alt="NLsqWF.png"></p> <p>其中<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>b</mi><mo>(</mo><mi>j</mi><mo separator="true">,</mo><mi>z</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">b(j,z)</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit">b</span><span class="mopen">(</span><span class="mord mathit" style="margin-right:0.05724em;">j</span><span class="mpunct">,</span><span class="mord mathit" style="margin-right:0.04398em;">z</span><span class="mclose">)</span></span></span></span>表示在全局最优组成的变量中，第<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.65952em;"></span><span class="strut bottom" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.05724em;">j</span></span></span></span>维变成<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>z</mi></mrow><annotation encoding="application/x-tex">z</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.04398em;">z</span></span></span></span></p> <p>图 2 展示了 CPSO-S 算法，它首先由 vandenbergh 和 Engelbrecht 在文献 9 中引入，这是一种将搜索空间精确划分为子空间的粒子群优化算法。扩展图 1 中介绍的约定，<strong><span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>P</mi><mi>j</mi></msub><mi mathvariant="normal">.</mi><msub><mi>x</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">P_j.x_i</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.969438em;vertical-align:-0.286108em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit" style="margin-right:0.13889em;">P</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.13889em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit" style="margin-right:0.05724em;">j</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mord mathrm">.</span><span class="mord"><span class="mord mathit">x</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span>现在指的是粒子群<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.65952em;"></span><span class="strut bottom" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.05724em;">j</span></span></span></span>中第<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.65952em;"></span><span class="strut bottom" style="height:0.65952em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">i</span></span></span></span>个粒子的位置</strong>，当有需要则可以将其替换为上下文环境向量的第<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.65952em;"></span><span class="strut bottom" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.05724em;">j</span></span></span></span>部分分量。对于<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">n</span></span></span></span>个粒子群，每个群都有一个全局最佳粒子<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>P</mi><mi>j</mi></msub><mi mathvariant="normal">.</mi><mover accent="true"><mrow><mi>y</mi></mrow><mo>^</mo></mover></mrow><annotation encoding="application/x-tex">P_j.\hat{y}</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.980548em;vertical-align:-0.286108em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit" style="margin-right:0.13889em;">P</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.13889em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit" style="margin-right:0.05724em;">j</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mord mathrm">.</span><span class="mord accent"><span class="vlist"><span style="top:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="mord textstyle cramped"><span class="mord mathit" style="margin-right:0.03588em;">y</span></span></span><span style="top:0em;margin-left:0.11112em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="accent-body"><span>^</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span>。函数<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>b</mi><mo>(</mo><mi>j</mi><mo separator="true">,</mo><mi>z</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">b(j,z)</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit">b</span><span class="mopen">(</span><span class="mord mathit" style="margin-right:0.05724em;">j</span><span class="mpunct">,</span><span class="mord mathit" style="margin-right:0.04398em;">z</span><span class="mclose">)</span></span></span></span>返回一个<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">n</span></span></span></span>维向量，该向量由所有群中的全局最佳向量串联而成，但第<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.65952em;"></span><span class="strut bottom" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.05724em;">j</span></span></span></span>分量被替换为<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>z</mi></mrow><annotation encoding="application/x-tex">z</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.04398em;">z</span></span></span></span>，其中<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>z</mi></mrow><annotation encoding="application/x-tex">z</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.04398em;">z</span></span></span></span>表示粒子群<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>P</mi><mi>j</mi></msub></mrow><annotation encoding="application/x-tex">P_j</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.969438em;vertical-align:-0.286108em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit" style="margin-right:0.13889em;">P</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.13889em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit" style="margin-right:0.05724em;">j</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span>中任何粒子的位置。</p> <p>该算法的优点是在向量中的每个分量更新后，对误差函数<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>f</mi></mrow><annotation encoding="application/x-tex">f</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.10764em;">f</span></span></span></span>进行求值，从而得到更细粒度的信用分配。<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>b</mi><mo>(</mo><mn>1</mn><mo separator="true">,</mo><msub><mi>P</mi><mi>i</mi></msub><mi mathvariant="normal">.</mi><mover accent="true"><mrow><mi>y</mi></mrow><mo>^</mo></mover><mo>)</mo></mrow><annotation encoding="application/x-tex">b(1, P_i.\hat{y})</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit">b</span><span class="mopen">(</span><span class="mord mathrm">1</span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.13889em;">P</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.13889em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mord mathrm">.</span><span class="mord accent"><span class="vlist"><span style="top:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="mord textstyle cramped"><span class="mord mathit" style="margin-right:0.03588em;">y</span></span></span><span style="top:0em;margin-left:0.11112em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="accent-body"><span>^</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mclose">)</span></span></span></span>将表示当前“最佳”上下文向量。请注意，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>f</mi><mo>(</mo><mi>b</mi><mo>(</mo><mn>1</mn><mo separator="true">,</mo><msub><mi>P</mi><mi>i</mi></msub><mi mathvariant="normal">.</mi><mover accent="true"><mrow><mi>y</mi></mrow><mo>^</mo></mover><mo>)</mo><mo>)</mo></mrow><annotation encoding="application/x-tex">f(b(1, P_i.\hat{y}))</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathit">b</span><span class="mopen">(</span><span class="mord mathrm">1</span><span class="mpunct">,</span><span class="mord"><span class="mord mathit" style="margin-right:0.13889em;">P</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.13889em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mord mathrm">.</span><span class="mord accent"><span class="vlist"><span style="top:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="mord textstyle cramped"><span class="mord mathit" style="margin-right:0.03588em;">y</span></span></span><span style="top:0em;margin-left:0.11112em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="accent-body"><span>^</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mclose">)</span><span class="mclose">)</span></span></span></span>是一个严格不递增的函数，因为它是由每个群的全局最佳粒子<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>P</mi><mi>j</mi></msub><mi mathvariant="normal">.</mi><mover accent="true"><mrow><mi>y</mi></mrow><mo>^</mo></mover></mrow><annotation encoding="application/x-tex">P_j.\hat{y}</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.980548em;vertical-align:-0.286108em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit" style="margin-right:0.13889em;">P</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.13889em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit" style="margin-right:0.05724em;">j</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mord mathrm">.</span><span class="mord accent"><span class="vlist"><span style="top:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="mord textstyle cramped"><span class="mord mathit" style="margin-right:0.03588em;">y</span></span></span><span style="top:0em;margin-left:0.11112em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="accent-body"><span>^</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span>组成的，只有当它们的适应度提高时，这些粒子才会更新。</p> <p>组中的每个粒子群只包含关于解向量的特定分量的信息；解向量的其余部分由其他<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">n-1</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.64444em;"></span><span class="strut bottom" style="height:0.72777em;vertical-align:-0.08333em;"></span><span class="base textstyle uncramped"><span class="mord mathit">n</span><span class="mbin">−</span><span class="mord mathrm">1</span></span></span></span>个粒子群提供。这促进了不同群体之间的合作，因为它们都有助于上下文向量。对合作机制的另一种解释是可能的。每一个粒子群代表一个不同的上下文，在这个上下文中，向量被计算在不同的上下文中，因此上下文向量本身的适应度是在不同的上下文中度量的。与产生最高适应度的粒子相对应的最成功的上下文将被保留以备将来使用。例如，一个 30 维的搜索空间会产生一个包含 30 个一维群的 CPSO-S 算法。在算法的一次迭代过程中，形成了不同的组合，而原始粒子群算法只产生了 30 个变量。CPSO-S 方法的优点是一次只修改一个组件，产生所需的细粒度搜索，有效地防止了“两步前进，一步后退”的情况。在 CPSO-S 算法中，由于使用来自不同群的不同成员形成的许多组合，解的多样性也显著增加。</p> <p>请注意，如果向量中的某些成分是相关的，它们应该被分组到同一个粒子群中（通过使用任意配置的划分机制），因为不同粒子群所做的独立更改将对相关变量产生不利影响。这导致一些群具有一维向量，而另一些群具有<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>c</mi></mrow><annotation encoding="application/x-tex">c</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">c</span></span></span></span>维向量，这在上述框架中很容易被允许。不幸的是，并不总是预先知道各向量之间的关系。一个简单的近似方法是一次盲目地取变量，希望一些相关变量最终会出现在同一个群中。图 3 展示了 CPSO-<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>S</mi><mi>k</mi></msub></mrow><annotation encoding="application/x-tex">S_k</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit" style="margin-right:0.05764em;">S</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.05764em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit" style="margin-right:0.03148em;">k</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span>算法，其中一个向量被分成了几个部分。注意，图 2 中所示的 CPSO-<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>S</mi><mi>k</mi></msub></mrow><annotation encoding="application/x-tex">S_k</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit" style="margin-right:0.05764em;">S</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.05764em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit" style="margin-right:0.03148em;">k</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span>算法实际上是 CPSO-S 算法的一个特例。分成各部分的数量<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>K</mi></mrow><annotation encoding="application/x-tex">K</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.68333em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.07153em;">K</span></span></span></span>也被称为分割因子。</p></div> <footer class="page-edit"><!----> <div class="last-updated"><span class="prefix">更新于:</span> <span class="time">12/31/2021, 11:53:22 PM</span></div></footer> <div class="page-nav"><p class="inner"><span class="prev">
      ←
      <a href="/paper/defense.html" class="prev">
        防御无人机
      </a></span> <span class="next"><a href="/paper/2020Auguest.html">
        2020年8月归档
      </a>
      →
    </span></p></div> </main></div><div class="global-ui"><!----></div></div>
    <script src="/assets/js/app.9e067b79.js" defer></script><script src="/assets/js/2.983eb755.js" defer></script><script src="/assets/js/51.f6160d52.js" defer></script>
  </body>
</html>
